package interview.tree;

// 人肉建树
public class TreeCreator
{

	public TreeNode createSampleTree()
	{
		TreeNode root = new TreeNode('A');
		root.setLeft(new TreeNode('B'));
		root.getLeft().setLeft(new TreeNode('D'));
		root.getLeft().setRight(new TreeNode('E'));
		root.getLeft().getRight().setLeft(new TreeNode('G'));
		root.setRight(new TreeNode('C'));
		root.getRight().setRight(new TreeNode('F'));
		return root;
	}

	public TreeNode createTree(String preOrder, String inOrder)
	{
		// 处理特殊情况
		if (preOrder.isEmpty())// 空传——>空树:没有结点
		{
			return null;
		}

		// 前序遍历的第一个点：根(A)
		char rootValue = preOrder.charAt(0);// 拿出第一个字符:根的value
		// 从中序遍历中寻找根(A)；找到后，切分左右
		int rootIndex = inOrder.indexOf(rootValue);
		// 知道左子树的长度(从中序那里看)
		// int leftSize = rootIndex;

		// 建树根：已经拿掉[0]
		TreeNode root = new TreeNode(rootValue);
		// 左子树：从[1]开始
		root.setLeft(createTree(preOrder.substring(1, 1 + rootIndex), inOrder.substring(0, rootIndex)));
		// 右子树
		root.setRight(createTree(preOrder.substring(1 + rootIndex), inOrder.substring(1 + rootIndex)));

		return root;
	}
}
